A Tight Rate Bound and a Matching Construction for Locally Recoverable Codes with Sequential Recovery From Any Number of Multiple Erasures

摘要

An $[n,k]$ code $\mathcal{C}$ is said to be locally recoverable in thepresence of a single erasure, and with locality parameter $r$, if each of the$n$ code symbols of $\mathcal{C}$ can be recovered by accessing at most $r$other code symbols. An $[n,k]$ code is said to be a locally recoverable codewith sequential recovery from $t$ erasures, if for any set of $s \leq t$erasures, there is an $s$-step sequential recovery process, in which at eachstep, a single erased symbol is recovered by accessing at most $r$ other codesymbols. This is equivalent to the requirement that for any set of $s \leq t$erasures, the dual code contain a codeword whose support contains thecoordinate of precisely one of the $s$ erased symbols. In this paper, a tightupper bound on the rate of such a code, for any value of number of erasures $t$and any value $r \geq 3$, of the locality parameter is derived. This boundproves an earlier conjecture due to Song, Cai and Yuen. While the bound isvalid irrespective of the field over which the code is defined, a matchingconstruction of {\em binary} codes that are rate-optimal is also provided,again for any value of $t$ and any value $r\geq3$.